﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution90
{
    IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> SubsetsWithDup(int[] nums)
    {


        IList<int> path = new List<int>();
        res.Add(new List<int>(path));
        bool[] used = new bool[nums.Length];
        Array.Sort(nums);
        DFS(nums, 0, path, used);
        return res;

    }
    //同一层的不可以重复使用【1，2】【1，2】不可以
    //同一个树枝的可以重复使用【1，2，2】可以
    private void DFS(int[] nums, int startIndex, IList<int> path, bool[] used)
    {

        

        for (int i = startIndex; i < nums.Length; i++)
        {
            if (i > startIndex &&  nums[i]==nums[i-1]&&used[i-1]==false)//第一个2用过了,跳过
            {

                continue;
            }
           
                path.Add(nums[i]);//本次循环使用过的数字不要使用了
                used[i] = true;
            res.Add(new List<int>(path));
            DFS(nums, i + 1, path, used);
                path.RemoveAt(path.Count - 1);
                used[i] = false;//本次循环，树层不可以重复
            
            
        }

       
    }private void DFS2(int[] nums, int startIndex, IList<int> path, bool[] used)
    {

        

        for (int i = startIndex; i < nums.Length; i++)
        {
            if (i>startIndex&& nums[i]==nums[i-1])//这样就可以，不需要used数组，本来就是只跳过一次循环，树枝没必要去重
            {

                continue;
            }
           
                path.Add(nums[i]);//本次循环使用过的数字不要使用了
                used[i] = true;
            res.Add(new List<int>(path));
            DFS2(nums, i + 1, path, used);
                path.RemoveAt(path.Count - 1);
                used[i] = false;//本次循环，树层不可以重复
            
            
        }


    }
    Dictionary<int, bool> map = new Dictionary<int, bool>();
    private void DFS3(int[] nums, int startIndex, IList<int> path, bool[] used)//错误
    {



        for (int i = startIndex; i < nums.Length; i++)
        {
            if (map.TryGetValue(nums[i], out bool value) && value == false)//说明用过了,但是只使用这一个flag，无法同时标注树层或者树枝
            {
                Console.WriteLine("跳过" + nums[i]);
                continue;
            }
            else//这个数字没有用过才用
            {
                map[nums[i]] = true;
                Console.WriteLine(nums[i]);
            }


            path.Add(nums[i]);//本次循环使用过的数字不要使用了

            res.Add(new List<int>(path));


            DFS3(nums, i + 1, path, used);
            path.RemoveAt(path.Count - 1);



        }


    }
}

public class Program90
{


    static void Main90(string[] args)
    {
        Solution90 solution = new Solution90();
        //int[] nums = [1, 2, 2];
        int[] nums = [4, 6, 7, 7];
        IList<IList<int>> res = solution.SubsetsWithDup(nums);
        for (int i = 0; i < res.Count; i++)
        {

            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();
        }
    }

}
